//
// Created by 啊汤哥 on 2025/6/25.
// 串的基本操作 -- 顺序存储
#include <cstdio>
#include <stdlib.h>
#define  MaxLen 255
typedef struct {
    char ch[MaxLen];
    int length;
}Strand;  // 静态数组实现

typedef struct {
    char *ch;
    int length;
}HString; // 动态数组实现

// 求子串 从字符串 s 中提取一个子字符串，并将结果存储在 sub 中 pos起始串的位置 len取的长度

bool SubString(Strand &sub, Strand s, int pos, int len) {
    // 检查提取的子字符串是否超出了原字符串的长度
    if (pos+len-1 > s.length) {
        return false;
    }
    for (int i = pos; i<pos+len; i++) {
        //新的存储从1开始 ex: 4-4+1 ---> 1位置开始存储
        sub.ch[i-pos+1] = s.ch[i];
    }
    // 设置提取字符的长度
    sub.length = len;
    return true;
}


// 子串的比较
int StrCompare(Strand s, Strand t) {
    for (int i =1; i<s.length && i<t.length; i++) {
        if (s.ch[i] != t.ch[i]) {
            // 返回的正负表示差值的大小
            return s.ch[i] - t.ch[i];
        }
    }
    // 如果字符串都相同 长度长的串更大
    return s.length - t.length;
}

// 求子串的长度
// 增加对Strand类型的重载
int StrLength(const Strand &s) {
    return s.length; // 直接返回结构体中的长度
}

// 定位 -- 第一次出现的位置
int Index(Strand s, Strand t) {
    int i = 1,n = StrLength(s),m = StrLength(t);
    Strand sub; //暂存的字符串
    while (i < n - m +1) {
        SubString(sub,s,i,m);
        if (StrCompare(sub,t)!=0) ++i;
        else return i;
    }
    return 0;
}

// 朴素匹配算法
int Pattern_Matching(Strand s, Strand t) {
    int i = 1;
    int j = 1;
    while (i< s.length && j <= t.length) {
        if (s.ch[i] == t.ch[i]) {
            i++,j++;
        }
        else {
            i = i - j + 2;
            j = 1; // 指针回退
        }
    }
    if (j > t.length) {
        return i-t.length;
    }
    return 0;
}

// KMP算法 没有回退 利用next数组进行匹配（主串指针不回溯）
int Index_KMP(Strand s, Strand t, int next[]) {
    int i = 1, j = 1;
    while (i<s.length && t.length) {
        if (j==0 || s.ch[i] == t.ch[i]) {
            i++,j++;
        }
        else {
            j = next[i];
        }
    }
    if (j > t.length) {
        return i-t.length;
    }
    return 0;
}